﻿/**
 * 该模块使用数组实现了 IDeque(T) 接口。
 * License: BSD
 * Authors: Lucifer (786325481@QQ.com)
 * Copyright: Copyright (C) 2008 Lucifer. All rights reserved.
 */

module system.collections.Deque;

import system.collections.IEqualityComparer;
import system.collections.EqualityComparer;
import system.collections.IEnumerable;
import system.collections.IEnumerator;
import system.collections.ICollection;
import system.collections.IQueue;
import system.collections.IDeque;

import system.Exception;
import system.Array;
import system.Traits;


/**
 * 使用数组实现 IDeque(T) 接口的可扩容的双端队列。
 * Comments:
 *		数组双端队列没有容量限制；它们可根据需要增加容量以支持使用。
 *		该集合不是线程安全的；在没有外部同步时，它们不支持多个线程的并发访问。
 *		禁止插入 null 元素。
 *		该集合既可用作(LIFO)堆栈，也可用作(FIFO)队列。
 *		该集合大多数操作以摊销的固定时间运行。
 *
 *		Note: 该集合的迭代器是快速失败的，但快速失败的行为并不能得到保证。
 *		      迭代器的快速失败行为应该仅用于检测 bug。
 *
 *		该集合可以正向或逆向顺序遍历，两种迭代均受支持。
 */
public class Deque(T) : IEnumerable!(T), ICollection!(T), IQueue!(T), IDeque!(T)
{
	private int theHead;
	private int theTail;
	private T[] theArray;

	private const int defaultCapacity = 16;
	/*
     * 新创建双端队列的最小容量。
     * 必须是 2 的指数倍。
     */
	private const int minCapacity = 8;

	///构造一个初始容量能够容纳 16 个元素的空数组双端队列。
	public this()
	{
		theArray = new T[defaultCapacity];
	}

	/**
	 * 构造一个初始容量能够容纳指定数量的元素的空数组双端队列。
	 * Params:
	 *		initialCapacity = 双端队列初始容量的下边界。
	 */
	public this(int initialCapacity)
	{
		this.allocateElements(initialCapacity);
	}

	/**
	 * 构造一个包含指定 collection 的元素的双端队列，
	 * 这些元素按 collection 的迭代器返回的顺序排列。
	 * Params:
	 *		collection = 要将其元素放入双端队列的 collection 。
	 */
	public this(IEnumerable!(T) collection)
	in
	{
		assert( collection !is null );
	}
	body
	{
		auto currentCollection = cast(ICollection!(T))collection;
		if(currentCollection !is null)
		{
			auto count = currentCollection.count;
			this.allocateElements(count);
			currentCollection.toArray(theArray);
		}
		else
		{
			theArray = new T[defaultCapacity];
			foreach(item; collection)
			{
				this.addLast(item);
			}
		}
	}

	/*
	 * 实现 IDeque(T) 接口。
	 */

	/**
	 * 将指定元素插入此双端队列的开头。
	 * Params:
	 *		item = 要添加的元素。
	 * Comments:
	 *		对于引用类型来说，不能添加 null 。
	 *		关于引用类型，详情请参考 system.Traits.IsReferenceType(T) 模板方法。
	 */
	public final void addFirst(T item)
	in
	{
		static if( IsReferenceType!(T) )
		{
			assert( item !is null );
		}
	}
	body
	{
		theArray[theHead = (theHead-1) & (theArray.length-1)] = item;
		if(theHead == theTail)
			this.doubleCapacity();
	}

	/**
	 * 将指定元素插入此双端队列的末尾。
	 * Params:
	 *		item = 要添加的元素。
	 * Comments:
	 *		对于引用类型来说，不能添加 null 。
	 *		关于引用类型，详情请参考 system.Traits.IsReferenceType(T) 模板方法。
	 *
	 * 		此方法等效于 add(T item) 。
	 */
	public final void addLast(T item)
	in
	{
		static if( IsReferenceType!(T) )
		{
			assert( item !is null );
		}
	}
	body
	{
		theArray[theTail] = item;
		if((theTail = (theTail+1) & (theArray.length-1)) == theHead)
			this.doubleCapacity();
	}

	/**
	 * 将指定元素插入此双端队列的开头。
	 * Params:
	 * 		item = 要添加的元素。
	 * Returns:
	 * 		true，此操作不会失败。
	 */
	public final bool tryAddFirst(T item)
	{
		addFirst(item);
		return true;
	}

	/**
	 * 将指定元素插入此双端队列的末尾。
	 * Params:
	 *		item = 要添加的元素。
	 * Returns:
	 *		true，此操作不会失败。
	 */
	public final bool tryAddLast(T item)
	{
		addLast(item);
		return true;
	}

	/**
	 * 获取并移除此双端队列所表示的队列的头。
	 * Returns:
	 * 		此双端队列所表示的队列的头。
	 * Throws:
	 *		InvalidOperationException，当双端队列为空时。
	 * Comments:
	 *		此方法与 tryRemove 的不同之处在于：如果此双端队列为空，它将抛出一个异常。
	 * 		此方法等效于 removeFirst 。
	 */
	public final T remove()
	{
		return removeFirst();
	}

	/**
	 * 获取并移除此双端队列所表示的队列的头。
	 * Params:
	 *		item = 此双端队列所表示的队列的头；如果此双端队列为空，则返回 T.init。
	 * Returns:
	 *		如果双端队列为空，返回 false；否则，返回 true 。
	 * Comments:
	 *		此方法等效于 tryRemoveFirst()。
	 */
	public final bool tryRemove(out T item)
	{
		return tryRemoveFirst(item);
	}

	/**
	 * 获取并移除此双端队列第一个元素。
	 * Returns:
	 *		此双端队列的头部。
	 * Throws:
	 *		InvalidOperationException，当双端队列为空时。
	 * Comments:
	 *		此方法与 tryRemoveFirst 唯一的不同在于：如果此双端队列为空，它将抛出一个异常。
	 */
	public final T removeFirst()
	{
		T item;
		auto result = tryRemoveFirst(item);
		if(result is false)
			throw new InvalidOperationException("No such an element. It means that the deque is empty.");
		return item;
	}

	/**
	 * 获取并移除此双端队列的最后一个元素。
	 * Throws:
	 *		InvalidOperationException，当双端队列为空时。
	 * Returns:
	 *		此双端队列的尾部。
	 * Comments:
	 *		此方法与 tryRemoveLast 唯一的不同在于：如果此双端队列为空，它将抛出一个异常。
	 */
	public final T removeLast()
	{
		T item;
		auto result = tryRemoveLast(item);
		if(result is false)
			throw new InvalidOperationException("No such an element. It means that the deque is empty.");
		return item;
	}

	/**
	 * 获取并移除此双端队列的第一个元素；如果此双端队列为空，则返回 T.init 。
	 * Params:
	 * 		item = 此双端队列的头部；如果此双端队列为空，则返回 T.init 。
	 * Returns:
	 *		如果双端队列为空，返回 false；否则，返回 true 。
	 */
	public final bool tryRemoveFirst(out T item)
	{
		if(this.isEmpty())
		{
			item = T.init;
			return false;
		}

		auto head = theHead;

		item = theArray[head];
		theArray[head] = T.init;

		theHead = (head+1) & (theArray.length-1);
		return true;
	}

	/**
	 * 获取并移除此双端队列的最后一个元素；如果此双端队列为空，则返回 T.init 。
	 * Params:
	 *		item = 此双端队列的尾部；如果此双端队列为空，则返回 T.init 。
	 * Returns:
	 *		如果双端队列为空，返回 false；否则，返回 true 。
	 */
	public final bool tryRemoveLast(out T item)
	{
		if(this.isEmpty())
		{
			item = T.init;
			return false;
		}

		auto tail = (theTail-1) & (theArray.length-1);

		item = theArray[tail];
		theArray[tail] = T.init;
		theTail = tail;

		return true;
	}

	/**
	 * 获取，但不移除此双端队列的第一个元素。
	 * Returns:
	 *		此双端队列的头部。
	 * Throws:
	 *		InvalidOperationException，当双端队列为空时。
	 * Comments:
	 *		此方法与 tryPeekFirst 唯一的不同在于：如果此双端队列为空，它将抛出一个异常。
	 */
	public final T peekFirst()
	{
		T item;
		auto result = tryPeekFirst(item);
		if(result is false)
			throw new InvalidOperationException("No such an element. It means that the deque is empty.");
		return item;
	}

	/**
	 * 获取，但不移除此双端队列的最后一个元素。
	 * Returns:
	 *		此双端队列的尾部。
	 * Throws:
	 *		InvalidOperationException，当双端队列为空时。
	 * Comments:
	 *	此方法与 tryPeekLast 唯一的不同在于：如果此双端队列为空，它将抛出一个异常。
	 */
	public final T peekLast()
	{
		T item;
		auto result = tryPeekLast(item);
		if(result is false)
			throw new InvalidOperationException("No such an element. It means that the deque is empty.");
		return item;
	}

	/**
	 * 获取，但不移除此双端队列的第一个元素。
	 * Params:
	 *		item = 此双端队列的头部；如果此双端队列为空，则返回 T.init。
	 * Returns:
	 * 		如果此双端队列为空，则返回 false；否则，返回 true。
	 */
	public final bool tryPeekFirst(out T item)
	{
		if(this.isEmpty())
		{
			item = T.init;
			return false;
		}
		item = theArray[theHead];
		return true;
	}

	/**
	 * 获取，但不移除此双端队列的最后一个元素。
	 * Params:
	 *		item = 此双端队列的尾部；如果此双端队列为空，则返回 T.init。
	 * Returns:
	 *		如果此双端队列为空，则返回 false；否则，返回 true。
	 */
	public final bool tryPeekLast(out T item)
	{
		if(this.isEmpty())
		{
			item = T.init;
			return false;
		}
		item = theArray[(theTail-1) & (theArray.length-1)];
		return true;
	}

	/**
	 * 移除此双端队列中第一次出现的指定元素（当从头部到尾部遍历双端队列时）。
	 * Params:
	 *		item = 要从此双端队列中移除的元素（如果存在）。
	 * Returns:
	 *		如果双端队列包含指定元素，则返回 true。
	 * Comments:
	 *		如果此双端队列不包含该元素，则不作更改。
	 *		更确切地讲，移除第一个满足等于 item 的元素（如果存在这样的元素）。
	 *		该方法使用默认相等比较器 DefaultEqualityComparer(T) 来进行相等性比较。
	 *		如果此双端队列包含指定的元素（或者此双端队列由于调用而发生了更改），则返回 true。
	 */
	public final bool removeFirstOccurrence(T item)
	in
	{
		static if( IsReferenceType!(T) )
		{
			assert( item !is null );
		}
	}
	body
	{
		int mask = theArray.length - 1;
		int head = theHead;
		int tail = theTail;
		auto comparer = DefaultEqualityComparer!(T).getInstance();
		for(; head != tail; head = (head+1) & mask)
		{
			if(comparer.equals(theArray[head], item))
			{
				deleteAt(head);
				return true;
			}
		}
		return false;
	}

	/**
	 * 移除此双端队列中最后一次出现的指定元素（当从头部到尾部遍历双端队列时）。
	 * Params:
	 *		item = 移除此双端队列中最后一次出现的指定元素（当从头部到尾部遍历双端队列时）。
	 * Returns:
	 *		如果双端队列包含指定元素，则返回 true。
	 * Comments:
	 *		如果此双端队列不包含该元素，则不作更改。
	 *		更确切地讲，移除最后一个满足等于 item 的元素（如果存在这样的元素）。
	 *		该方法使用默认相等比较器 DefaultEqualityComparer(T) 来进行相等性比较。
	 *		如果此双端队列包含指定的元素（或者此双端队列由于调用而发生了更改），则返回 true。
	 */
	public final bool removeLastOccurrence(T item)
	in
	{
		static if( IsReferenceType!(T) )
		{
			assert( item !is null );
		}
	}
	body
	{
		int mask = theArray.length - 1;
		int head = theHead;
		int tail = theTail;
		auto comparer = DefaultEqualityComparer!(T).getInstance();
		for(tail = (tail-1) & mask; head != tail; tail = (tail-1) & mask)
		{
			if(comparer.equals(theArray[tail], item))
			{
				deleteAt(tail);
				return true;
			}
		}
		return false;
	}

	/**
	 * 将元素推入此双端队列所表示的堆栈。换句话说，将元素插入此双端队列的开头。
	 * Params:
	 *		item = 要推入的元素。
	 * Comments:
	 *		此方法等效于 addFirst(T item)。
	 */
	public final void push(T item)
	{
		addFirst(item);
	}

	/**
	 * 从此双端队列所表示的堆栈中弹出一个元素。换句话说，移除并返回此双端队列第一个元素。
	 * Returns:
	 *		此双端队列开头的元素（它是此双端队列所表示的堆栈的顶部）。
	 * Throws:
	 *		InvalidOperationException，如果此双端队列为空。
	 * Comments:
	 *		此方法等效于 removeFirst() 。
	 */
	public final T pop()
	{
		return removeFirst();
	}

	/*
	 * 实现 IQueue(T) 接口。
	 */

	///等效于 add(T item)。
	public final bool enqueue(T item)
	{
		addLast(item);
		return true;
	}

	///等效于 removeFirst()。
	public final T dequeue()
	{
		return removeFirst();
	}

	///等效于 peekFirst()。
	public final T peek()
	{
		return peekFirst();
	}

	///等效于 tryAddLast(T item)。
	public final bool tryEnqueue(T item)
	{
		return tryAddLast(item);
	}

	///等效于 tryRemoveFirst()。
	public final bool tryDequeue(out T item)
	{
		return tryRemoveFirst(item);
	}

	///等效于 tryPeekFirst()。
	public final bool tryPeek(out T item)
	{
		return tryPeekFirst(item);
	}

	/*
	 * 实现 ICollection(T) 接口。
	 */

	/**
	 * 如果此双端队列未包含任何元素，则返回 true。
	 */
	public final bool isEmpty()
	{
		return theHead == theTail;
	}

	/**
	 * 返回此双端队列中的元素数。
	 */
	public final int count()
	{
		return (theTail - theHead) & (theArray.length-1);
	}

	///查看该集合是否只读。
	public final bool isReadOnly()
	{
		return false;
	}

	/**
	 * 将指定元素插入此双端队列的末尾。
	 * Params:
	 *		item = 要添加的元素。
	 * Returns:
	 * 		true。
	 */
	public final bool add(T item)
	{
		return tryAddLast(item);
	}

	///等效于 tryAddLast(T item)。
	public final bool tryAdd(T item)
	{
		return tryAddLast(item);
	}

	///从此双端队列中移除所有元素。在此调用返回之后，该双端队列将为空。
	public final void clear()
	{
		if(!this.isEmpty())
		{
			if(theHead < theTail)
			{
				Array.clear!(T)(theArray[theHead..theTail]);
			}
			else
			{
				Array.clear!(T)(theArray[theHead..$]);
				Array.clear!(T)(theArray[0..$]);
			}

			theHead = theTail = 0;
		}
	}

	///等效于 removeFirstOccurrence(T item)。
	public final bool remove(T item)
	{
		return this.removeFirstOccurrence(item);
	}

	///如果此双端队列包含指定元素，则返回 true。
	public final bool contains(T item)
	in
	{
		static if( IsReferenceType!(T) )
		{
			assert( item !is null );
		}
	}
	body
	{
		auto head = theHead;
		auto tail = theTail;
		int mask = theArray.length - 1;
		auto comparer = DefaultEqualityComparer!(T).getInstance();
		for(; head != tail; head = (head+1) & mask)
		{
			if(comparer.equals(theArray[head], item))
				return true;
		}
		return false;
	}

	///返回一个以恰当顺序包含此双端队列所有元素的数组(如果指定的数组容量不小于双端队列所包含的元素数)。
	public final void toArray(T[] array)
	in
	{
		assert( array !is null );
	}
	body
	{
		if(theHead < theTail)
		{
			Array.copy!(T)(theArray[theHead..$], array[0..$] , this.count());
		}
		else
		{
			auto size = theArray.length - theHead;
			Array.copy!(T)(theArray[theHead..$], array[0..$], size);
			Array.copy!(T)(theArray[0..$], array[size..$], theTail);
		}
	}

	/*
	 * 实现 IEnumerable(T) 接口。
	 */

	/**
	 * 返回在此双端队列的元素上进行迭代的迭代器。
	 * 元素将按从第一个（头）到最后一个（尾）的顺序进行排序。
	 * 这与元素出列（通过连续调用 remove()）或弹出（通过连续调用 pop()）的顺序相同。
	 */
	public final Enumerator getEnumerator()
	{
		return new Enumerator();
	}

	/**
	 * 返回以逆向顺序在此双端队列的元素上进行迭代的迭代器。
	 * 元素将按从最后一个（尾部）到第一个（头部）的顺序返回。
	 */
	public final DescendingEnumerator getDescendingEnumerator()
	{
		return new DescendingEnumerator();
	}

	public final int opApply (int delegate (ref T value) dg)
	{
		auto scope enumerator = new Enumerator();
		int result = 0;
		while(enumerator.moveNext())
		{
			auto value = enumerator.current();
			if( (result = dg(value)) != 0 )
				break;
		}
		return result;
	}

	public final int opApplyReverse(int delegate(ref T value) dg)
	{
		auto scope enumerator = new DescendingEnumerator();
		int result = 0;
		while(enumerator.moveNext())
		{
			auto value = enumerator.current();
			if( (result = dg(value)) != 0 )
				break;
		}
		return result;
	}

	/**
     * Throws:
     * 		InvalidOperationException，当在遍历对象时修改了集合或集合为空时。
     */
	public final class Enumerator : IEnumerator!(T)
	{
		private int head;
		private int tail;

		package this()
		{
			head = theHead;
			tail = theTail;
		}

		public bool moveNext()
		{
			return head != tail;
		}

		public T current()
		{
			if(head == tail)
				throw new InvalidOperationException("No such an element. It means that the deque is empty.");

			auto result = theArray[head];

			//Note: 这个检测并不能检测到所有可能的修改
			static if( IsReferenceType!(T) )
			{
				if( theTail != tail || result is null )
				{
					throw new InvalidOperationException("Collection was modified, enumeration operation can not execute.");
				}
			}
			else
			{
				if( theTail != tail )
				{
					throw new InvalidOperationException("Collection was modified, enumeration operation can not execute.");
				}
			}

			head = (head+1) & (theArray.length-1);

			return result;
		}

		public void reset()
		{
			if( theTail != tail )
			{
				throw new InvalidOperationException("Collection was modified, enumeration operation can not execute.");
			}
			head = theHead;
			tail = theTail;
		}
	}

	/**
     * Throws:
     * 		InvalidOperationException，当在遍历对象时修改了集合或集合为空时。
     */
	public final class DescendingEnumerator : IEnumerator!(T)
	{
		private int head;
		private int tail;

		package this()
		{
			head = theHead;
			tail = theTail;
		}

		public bool moveNext()
		{
			return head != tail;
		}

		public T current()
		{
			if(head == tail)
				throw new InvalidOperationException("No such an element. It means that the deque is empty.");

			tail = (tail-1) & (theArray.length-1);

			auto result = theArray[tail];

			static if( IsReferenceType!(T) )
			{
				if( head != theHead || result is null )
				{
					throw new InvalidOperationException("Collection was modified, enumeration operation can not execute.");
				}
			}
			else
			{
				if( head != theHead )
				{
					throw new InvalidOperationException("Collection was modified, enumeration operation can not execute.");
				}
			}

			return result;
		}

		public void reset()
		{
			if( head != theHead )
			{
				throw new InvalidOperationException("Collection was modified, enumeration operation can not execute.");
			}
			head = theHead;
			tail = theTail;
		}
	}

	//构造一个空数组以便能容纳指定容量
	private void allocateElements(int capacity)
	{
		int initialCapacity = minCapacity;
		//寻找最佳 2 的指数倍容量
		if(capacity >= initialCapacity)
		{
			initialCapacity = capacity;
			initialCapacity |= (initialCapacity >>> 1);
			initialCapacity |= (initialCapacity >>> 2);
			initialCapacity |= (initialCapacity >>> 4);
			initialCapacity |= (initialCapacity >>> 8);
			initialCapacity |= (initialCapacity >>> 16);

			initialCapacity++;

			//溢出保护
			if(initialCapacity < 0)
				initialCapacity >>>= 1;
		}
		theArray = new T[initialCapacity];
	}

	/*
	 * 双倍扩容双端队列，只在队列充满时。
	 * 比如队列头和尾相等时。
	 */
	private void doubleCapacity()
	{
		assert(theHead == theTail);

		int head = theHead;
		int capacity = theArray.length;
		int right = capacity - head;
		int newCapacity = capacity << 1;

		if(newCapacity < 0)
			throw new InvalidOperationException("Sorry, deque is too big.");

		T[] array = new T[newCapacity];

		Array.copy!(T)(theArray[head..$], array[0..$], right);
		Array.copy!(T)(theArray[0..$], array[right..$], head);

		theArray = array;
		theHead = 0;
		theTail = capacity;
	}

	/*
	 * 删除内部数组指定索引处的元素，并按需调整头尾指示位置。
	 * 如果元素向后移动则返回 true，否则返回 false。
	 */
	private bool deleteAt(int index)
	{
		auto array = this.theArray;
		int mask = array.length-1;
		int head = theHead;
		int tail = theTail;
		int front = (index - head) & mask;
		int back = (tail - index) & mask;

		if(back >= ((tail-head) & mask))
			throw new InvalidOperationException("Collection was modified, enumeration operation can not execute.");

		if(front < back)
		{
			if(head <= index)
			{
				Array.copy!(T)(array[head..$], array[head+1..$], front);
			}
			else
			{
				Array.copy!(T)(array[0..$], array[1..$], index);
				array[0] = array[mask];
				Array.copy!(T)(array[head..$], array[head+1..$], mask-head);
			}

			array[head] = T.init;
			theHead = (head+1) & mask;
			return false;
		}
		else
		{
			if(index < tail)
			{
				Array.copy!(T)(array[index+1..$], array[index..$], back);
				theTail = tail-1;
			}
			else
			{
				Array.copy!(T)(array[index+1..$], array[index..$], mask-index);
				array[mask] = array[0];
				Array.copy!(T)(array[1..$], array[0..$], tail);
				theTail = (tail-1) & mask;
			}
			return true;
		}
	}
}

unittest
{
	class TestDeque
	{
		void testStack()
		{
			auto deque = new Deque!(int)();

			assert(deque.count == 0);

			deque.push(1);
			deque.push(2);
			deque.push(3);

			assert(deque.count == 3);

			assert(deque.pop() == 3);
			assert(deque.pop() == 2);
			assert(deque.pop() == 1);

			assert(deque.count == 0);
			assert(deque.isEmpty());

			deque.push(1);
			deque.push(2);

			assert(deque.peek() == 2);
			assert(deque.peekLast() == 1);

			deque.clear();

			assert(deque.count == 0);
			assert(deque.isEmpty());
		}

		void testQueue()
		{
			auto deque = new Deque!(int)(3);

			assert(deque.count == 0);
			assert(deque.isEmpty());

			deque.enqueue(1);
			deque.enqueue(2);
			deque.enqueue(3);

			assert(deque.dequeue() == 1);
			assert(deque.dequeue() == 2);
			assert(deque.dequeue() == 3);

			assert(deque.count == 0);
			assert(deque.isEmpty());
		}

		void testForEach()
		{
			auto deque = new Deque!(int)(3);

			deque.add(1);
			deque.add(2);
			deque.add(3);

			int i = 0;

			foreach(item; deque)
			{
				assert(item == ++i);
			}

			foreach_reverse(item; deque)
			{
				assert(item == i--);
			}
		}
	}

	auto test = new TestDeque();
	test.testStack();
	test.testQueue();
	test.testForEach();
}
